#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        int len = 0;
        vector<int> tmp;
        tmp.resize(nums.size() + 1, 0);

        tmp[0] = (int)2e-9;

        for (int i = 0; i < nums.size(); ++i)
        {
            int l = 0, r = len;
            while (l < r)
            {
                int mid = (l + r + 1) >> 1;
                if (tmp[mid] < nums[i])
                {
                    l = mid;
                }
                else
                    r = mid - 1;
            }
            len = max(len, r + 1);
            tmp[r + 1] = nums[i];
        }
        return len;
    }
};